{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 计算学习理论\n",
    "&emsp;&emsp;上篇主要介绍了常用的特征选择方法及稀疏学习。首先从相关/无关特征出发引出了特征选择的基本概念，接着分别介绍了子集搜索与评价、过滤式、包裹式以及嵌入式四种类型的特征选择方法。子集搜索与评价使用的是一种优中生优的贪婪算法，即每次从候选特征子集中选出最优子集；过滤式方法计算一个相关统计量来评判特征的重要程度；包裹式方法将学习器作为特征选择的评价准则；嵌入式方法则是通过$L1$正则项将特征选择融入到学习器参数优化的过程中。最后介绍了稀疏表示与压缩感知的核心思想：稀疏表示利用稀疏矩阵的优良性质，试图通过某种方法找到原始稠密矩阵的合适稀疏表示；压缩感知则试图利用可稀疏表示的欠采样信息来恢复全部信息。本篇将讨论一种为机器学习提供理论保证的学习方法——计算学习理论。  \n",
    "\n",
    "&emsp;&emsp;计算学习理论（computational learning theory）是通过“计算”来研究机器学习的理论，简而言之，其目的是分析学习任务的本质，例如：**在什么条件下可进行有效的学习，需要多少训练样本能获得较好的精度等，从而为机器学习算法提供理论保证**。  \n",
    "&emsp;&emsp;首先我们回归初心，再来谈谈经验误差和泛化误差。假设给定训练集$D$，其中所有的训练样本都服从一个未知的分布$T$，且它们都是在总体分布$T$中独立采样得到，即**独立同分布**（independent and identically distributed，i.i.d.），在《贝叶斯分类器》中我们已经提到：独立同分布是很多统计学习算法的基础假设，例如最大似然法，贝叶斯分类器，高斯混合聚类等，简单来理解独立同分布：每个样本都是从总体分布中独立采样得到，而没有拖泥带水。例如现在要进行问卷调查，要从总体人群中随机采样，看到一个美女你高兴地走过去，结果她男票突然冒了出来，说道：you jump，i jump，于是你本来只想调查一个人结果被强行撒了一把狗粮得到两份问卷，这样这两份问卷就不能称为独立同分布了，因为它们的出现具有强相关性。  \n",
    "&emsp;&emsp;回归正题，**泛化误差指的是学习器在总体上的预测误差，经验误差则是学习器在某个特定数据集$D$上的预测误差**。在实际问题中，往往我们并不能得到总体且数据集$D$是通过独立同分布采样得到的，因此我们常常使用经验误差作为泛化误差的近似。  \n",
    "**泛化误差：**$E(h;D)=P_{x \\sim D}(h(x) \\neq y)$  \n",
    "**经验误差：**$\\displaystyle \\hat{E}(h;D)=\\frac{1}{m} \\sum_{i=1}^m I(h(x_i) \\neq y_i)$\n",
    "\n",
    "### PAC学习\n",
    "&emsp;&emsp;在高中课本中，我们将**函数定义为：从自变量到因变量的一种映射；对于机器学习算法，学习器也正是为了寻找合适的映射规则**，即如何从条件属性得到目标属性。从样本空间到标记空间存在着很多的映射，我们将每个映射称之为**概念**（concept），定义：\n",
    "\n",
    "> - 若概念$c$对任何样本$x$满足$c(x)=y$，则称$c$为**目标概念**，即最理想的映射，所有的目标概念构成的集合称为**“概念类”**；  \n",
    "- 给定学习算法，它所有可能映射/概念的集合称为**“假设空间”**，其中单个的概念称为**“假设”**（hypothesis）；  \n",
    "- 若一个算法的假设空间包含目标概念，则称该数据集对该算法是**可分**（separable）的，亦称**一致**（consistent）的；\n",
    "- 若一个算法的假设空间不包含目标概念，则称该数据集对该算法是**不可分**（non-separable）的，或称**不一致**（non-consistent）的。\n",
    "\n",
    "&emsp;&emsp;举个简单的例子：对于非线性分布的数据集，若使用一个线性分类器，则该线性分类器对应的假设空间就是空间中所有可能的超平面，显然假设空间不包含该数据集的目标概念，所以称数据集对该学习器是不可分的。给定一个数据集$D$，我们希望模型学得的假设$h$尽可能地与目标概念一致，这便是**概率近似正确** (Probably Approximately Correct，简称PAC)的来源，即以较大的概率学得模型满足误差的预设上限。\n",
    "> - **定义12.1 PAC辨识**（PAC Identify）：对$0<\\epsilon, \\delta < 1$，所有$c \\in C$和分布$D$，若存在学习算法$L$，其输出假设$h \\in H$满足$$P(E(h) \\leqslant \\epsilon) \\geqslant 1 - \\delta$$等价于$E(c)=0，P\\{(E(h)-E(c)) \\leqslant e\\} \\geqslant 1 - \\delta$，则称学习算法$L$能从假设空间$H$中PAC识别概念类$C$（**即目标概念的有效近似**）。  \n",
    "- **定义12.2 PAC可学习**（PAC Learnable）：令$m$表示从分布$D$中独立同分布采样得到的样例数目，$0 < \\epsilon, \\delta < 1$，对所有分布$D$，若存在学习算法$L$和多项式函数$\\text{poly}(\\cdot,\\cdot,\\cdot,\\cdot)$，使得对于任何$m \\geqslant \\text{poly}(1/\\epsilon, 1/\\delta, \\text{size}(x), \\text{size}(c))$，$L$能从假设空间$H$中PAC识别概念类$C$，则称概念类$C$对假设空间$H$而言是PAC可学习的，又是也简称概念类$C$是PAC可学习的。  \n",
    "- **定义12.3 PAC学习算法**（PAC Learning Algorithm）：若学习算法$L$使概念类$C$为PAC可学习的，且$L$的运行时间也是多项式函数$\\text{poly}(1/\\epsilon, 1/\\delta, \\text{size}(x), \\text{size}(c))$，则称概念类$C$是高效PAC可学习（efficiently PAC learnable）的，称$L$为概念类$C$的PAC学习算法。  \n",
    "- **定义12.4 样本复杂度**（Sample Complexity）：满足$PAC$学习算法$L$所需的$m \\geqslant \\text{poly}(1/\\epsilon, 1/\\delta, \\text{size}(x), \\text{size}(c))$中最小的$m$称为学习算法$L$的样本复杂度。\n",
    "\n",
    "&emsp;&emsp;上述关于PAC的几个定义层层相扣：定义12.1表达的是对于某种学习算法，如果能以一个置信度学得假设满足泛化误差的预设上限，则称该算法能PAC辨识概念类，即该算法的输出假设已经十分地逼近目标概念。定义12.2则将样本数量考虑进来，当样本超过一定数量时，学习算法总是能PAC辨识概念类，则称概念类为PAC可学习的。定义12.3将学习器运行时间也考虑进来，若运行时间为多项式时间，则称PAC学习算法。  \n",
    "&emsp;&emsp;显然，PAC学习中的一个关键因素就是**假设空间的复杂度**，对于某个学习算法，**若假设空间越大，则其中包含目标概念的可能性也越大，但同时找到某个具体概念的难度也越大**，一般假设空间分为有限假设空间与无限假设空间。\n",
    "\n",
    "### 有限假设空间\n",
    "#### 可分情形\n",
    "&emsp;&emsp;可分或一致的情形指的是：**目标概念包含在算法的假设空间中**。对于目标概念，在训练集$D$中的经验误差一定为0，因此首先我们可以想到的是：不断地剔除那些出现预测错误的假设，直到找到经验误差为0的假设即为目标概念。但**由于样本集有限，可能会出现多个假设在$D$上的经验误差都为0，因此问题转化为：需要多大规模的数据集$D$才能让学习算法以置信度的概率从这些经验误差都为0的假设中找到目标概念的有效近似**。\n",
    "\n",
    "> 对于算法的某个输出假设泛化误差大于$e$，且在数据集上表现完美的概率： \n",
    "$$\\begin{aligned} P\\left((h(x_1)=y_1) \\wedge \\ldots \\wedge \\left(h(x_m)=y_m\\right)\\right) \n",
    "&=(1-P(h(x) \\neq y))^m \\\\ \n",
    "&<(1-\\epsilon)^m \\end{aligned}$$所有这样的假设出现的概率，实际上中间有省略，假设有$k$个泛化误差大于$e$的假设，$P(h \\in H:\\ldots) < k(1 -e)^m < |H|(1-e)^m$：$$\\begin{aligned} P(h \\in H:E(h) > \\epsilon \\wedge \\hat{E}(h)=0) \n",
    "& < |H|(1-\\epsilon)^m \\\\\n",
    "& < |H|e^{-m\\epsilon} \\end{aligned}$$令上式不大于$\\delta$（即目标概念的有效近似），即$$|H|e^{-m\\epsilon} \\leqslant \\delta$$可得$$m \\geqslant \\frac{1}{\\epsilon} (\\ln |H| + \\ln \\frac{1}{\\delta})$$\n",
    "\n",
    "&emsp;&emsp;通过上式可以得知：**对于可分情形的有限假设空间，目标概念都是PAC可学习的，即当样本数量满足上述条件之后，在与训练集一致的假设中总是可以在$1-\\delta$概率下找到目标概念的有效近似。**\n",
    "\n",
    "#### 不可分情形\n",
    "&emsp;&emsp;不可分或不一致的情形指的是：**目标概念不存在于假设空间中**，这时我们就不能像可分情形时那样从假设空间中寻找目标概念的近似。但**当假设空间给定时，必然存一个假设的泛化误差最小，若能找出此假设的有效近似也不失为一个好的目标，这便是不可知学习(agnostic learning)的来源。**\n",
    "> **定义12.5 不可知PAC可学习**（agnostic PAC learnable）：令$m$表示从分布$D$中独立同分布采样得到的样例数目，$0<\\epsilon, \\delta < 1$，对所有分布$D$，若存在学习算法$L$和多项式函数$\\text{poly}(\\cdot,\\cdot,\\cdot,\\cdot)$，使得对于任何$m \\geqslant \\text{poly}(1/\\epsilon, 1/\\delta, \\text{size}(x), \\text{size}(c))$，$L$能从假设空间$H$中输出满足下式的假设$h$：$$P\\left(E(h)-\\min _{h' \\in H} E(h') \\leqslant \\epsilon\\right) \\geqslant 1-\\delta$$则称假设空间$H$是不可知PAC可学习的。（**即以置信度的概率找到假设空间泛化误差最小的假设的有效近似**）\n",
    "\n",
    "&emsp;&emsp;这时候便要用到**Hoeffding不等式**，以下给出单个假设的误差概率：$$\n",
    "P(\\widehat{E}(h)-E(h) \\geqslant \\epsilon) \\leqslant \\exp (-2 m \\epsilon^2) \\\\ \n",
    "P(E(h)-\\widehat{E}(h) \\geqslant \\epsilon) \\leqslant \\exp (-2 m \\epsilon^2) \\\\ \n",
    "P(|E(h)-\\widehat{E}(h)| \\geqslant \\epsilon) \\leqslant 2 \\exp (-2 m \\epsilon^2)$$\n",
    "&emsp;&emsp;对于假设空间中的所有假设，出现泛化误差与经验误差之差大于e的概率和为：$$\\sum_{h \\in H} P(|E(h)-\\widehat{E}(h)|>\\epsilon) \\leqslant 2|H| \\exp (-2 m \\epsilon^2)$$\n",
    "&emsp;&emsp;因此，令不等式的右边小于（等于）$\\delta$，便可以求出满足泛化误差与经验误差相差小于$e$所需的最少样本数，同时也可以求出泛化误差界。$$\n",
    "m \\geqslant \\frac{1}{2 \\epsilon^2}(\\ln |H|+\\ln (1 / \\delta)) \\\\\n",
    "P(|E(h)-\\widehat{E}(h)| \\leqslant \\sqrt{\\frac{\\ln |H|+\\ln (2 / \\delta)}{2 m}}) \\geqslant 1-\\delta $$\n",
    "\n",
    "### VC维\n",
    "&emsp;&emsp;现实中的学习任务通常都是无限假设空间，例如d维实数域空间中所有的超平面等，因此要对此种情形进行可学习研究，需要度量**假设空间的复杂度**。这便是**VC维**（Vapnik-Chervonenkis dimension）的来源。在介绍VC维之前，需要引入两个概念：\n",
    "\n",
    "> - **增长函数**：对于给定数据集D，假设空间中的每个假设都能对数据集的样本赋予标记，因此一个假设对应着一种打标结果，不同假设对D的打标结果可能是相同的，也可能是不同的。随着样本数量m的增大，假设空间对样本集D的打标结果也会增多，增长函数则表示假设空间对m个样本的数据集D打标的最大可能结果数，因此**增长函数描述了假设空间的表示能力与复杂度。** $$\\displaystyle \\Pi_{\\mathcal{H}}(m)=\\max _{\\{x_1, \\ldots, x_m\\} \\subseteq X}\\left|\\left\\{\\left(h(x_1), \\ldots, h(x_m)\\right) | h \\in H\\right\\}\\right|$$对于不同的数据集，增长函数可能不相同。  \n",
    "- **打散**：例如对二分类问题来说，m个样本最多有2^m个可能结果，每种可能结果称为一种**“对分”**，若假设空间能实现数据集D的所有对分，则称数据集能被该假设空间打散。  \n",
    "\n",
    "&emsp;&emsp;**因此尽管假设空间是无限的，但它对特定数据集打标的不同结果数是有限的，假设空间的VC维正是它能打散的最大数据集大小**。通常这样来计算假设空间的VC维：若存在大小为$d$的数据集能被假设空间打散，但不存在任何大小为$d+1$的数据集能被假设空间打散，则其VC维为$d$。  \n",
    "$$\\text{VC}(H)=\\max \\left\\{m : \\Pi_{H}(m)=2^{m}\\right\\}$$\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../images/12-1-Linear-Partition-on-Two-Dimensional-Real-Plane.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图12-1 二维实平面上所有线性划分构成的假设空间的VC维为3</div></center>\n",
    "\n",
    "&emsp;&emsp;同时书中给出了假设空间VC维与增长函数的两个关系：\n",
    "$\\displaystyle \\Pi_{H}(m) \\leqslant \\sum_{i=0}^d\\left(\\begin{array}{c}{m} \\\\ {i}\\end{array}\\right) \\tag{1}$  \n",
    "$\\displaystyle \\Pi_{H}(m) \\leqslant\\left(\\frac{e \\cdot m}{d}\\right)^{d} \\tag{2}$  \n",
    "&emsp;&emsp;直观来理解(1)式也十分容易： 首先假设空间的VC维是$d$，说明当$m \\leqslant d$时，增长函数与$2^m$相等，例如：当$m=d$时，右边的组合数求和刚好等于$2^d$；而当$m=d+1$时，右边等于$2^(d+1)-1$，十分符合VC维的定义，同时也可以使用数学归纳法证明；(2)式则是由(1)式直接推导得出。  \n",
    "&emsp;&emsp;在有限假设空间中，根据**Hoeffding**不等式便可以推导得出学习算法的泛化误差界；但在无限假设空间中，由于假设空间的大小无法计算，只能通过增长函数来描述其复杂度，因此无限假设空间中的泛化误差界需要引入增长函数。  \n",
    "> **定理12.2** 对假设空间$H,m \\in N, 0 < \\epsilon < 1$和任意$h \\in H$有$$P(|E(h)-\\widehat{E}(h)|>\\epsilon) \\leqslant 4 \\Pi_{H}(2 m) \\exp \\left(-\\frac{m \\epsilon^2}{8}\\right)$$将(2)式代入定理便可得无限假设空间的泛化误差界：$$\n",
    "P(E(h)-\\widehat{E}(h) \\leqslant \\sqrt{\\frac{\\displaystyle 8 d \\ln \\frac{2 e m}{d}+8 \\ln \\frac{4}{\\delta}}{m}}) \\geqslant 1-\\delta\n",
    "$$\n",
    "上界（多余此数目则可学到）：$\\displaystyle m \\geqslant \\frac{1}{\\epsilon}\\left(4 \\log_{2}(2 / \\delta)+8 V C(H) \\log _{2}(13 / \\epsilon)\\right)$  \n",
    "下界（少于此数目则学 ）:$\\displaystyle \\max \\left[\\frac{1}{\\epsilon} \\log (1 / \\delta), \\frac{V C(C)-1}{32 \\epsilon}\\right]$\n",
    "\n",
    "&emsp;&emsp;上式给出了基于VC维的泛化误差界，同时也可以计算出满足条件需要的样本数（样本复杂度）。若学习算法满足**经验风险最小化原则（ERM）**，即学习算法的输出假设$h$在数据集$D$上的经验误差最小，可证明：**任何VC维有限的假设空间都是（不可知）PAC可学习的，换而言之：若假设空间的最小泛化误差为0即目标概念包含在假设空间中，则是PAC可学习，若最小泛化误差不为0，则称为不可知PAC可学习。**\n",
    "\n",
    "### 稳定性\n",
    "&emsp;&emsp;稳定性考察的是当算法的输入发生变化时，输出是否会随之发生较大的变化，输入的数据集$D$有以下两种变化：\n",
    "\n",
    "- $D^{\\backslash i}$表示移除$D$中第$i$个样例得到的集合：$$D^{\\backslash i}=\\{z_1, z_2, \\ldots, z_{i-1}, z_{i+1}, \\ldots, z_m\\}$$\n",
    "- $D^i$表示替换$D$中第$i$个样例得到的集合：$$D^i=\\{z_1, z_2, \\ldots, z_{i-1}, z'_i ,z_{i+1}, \\ldots, z_m\\}$$其中$z'_i=(x'_i,y'_i),x'_i$服从分布$D$并独立于$D$  \n",
    "\n",
    "若对数据集中的任何样本$z$，满足：$$|\\ell(L_D, z)-\\ell(L_{D^{\\backslash i}}, z)| \\leqslant \\beta, \\quad i=1,2, \\ldots, m$$即原学习器和剔除一个样本后生成的学习器对$z$的损失之差保持$\\beta$稳定，称学习器关于损失函数满足**$\\beta$-均匀稳定性**。同时若损失函数有上界，即原学习器对任何样本的损失函数不超过$M$，则有如下定理：\n",
    "$$\\ell(L, D) \\leqslant \\hat{\\ell}(L, D)+2 \\beta+(4 m \\beta+M) \\sqrt{\\frac{\\ln (1 / \\delta)}{2 m}} \\\\\n",
    "\\ell(L, D) \\leqslant {\\ell}_{loo}(L, D)+\\beta+(4 m \\beta+M) \\sqrt{\\frac{\\ln (1 / \\delta)}{2 m}}$$其中$\\ell(L,D)$为泛化损失，$\\hat{\\ell}(L, D)$为经验损失，${\\ell}_{loo}(L, D)$为留一损失。\n",
    "\n",
    "&emsp;&emsp;事实上，**若学习算法符合经验风险最小化原则（ERM）且满足β-均匀稳定性，则假设空间是可学习的**。稳定性通过损失函数与假设空间的可学习联系在了一起，区别在于：假设空间关注的是经验误差与泛化误差，需要考虑到所有可能的假设；而稳定性只关注当前的输出假设。\n",
    "\n",
    "&emsp;&emsp;在此，计算学习理论就介绍完毕，一看这个名字就知道这一章比较偏底层理论了，最终还是咬着牙看完了它，这里引用一段小文字来梳理一下现在的心情：“孤岂欲卿治经为博士邪？但当涉猎，见往事耳”，就当扩充知识体系吧。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
